package com.wenhao.leetcode.medium;

import java.util.*;

/**
 * 题目：https://leetcode-cn.com/problems/remove-duplicate-letters/
 * 去除重复字母
 *
 * 这一题 他妈的 过一段时间再看吧
 *
 * 我以为栈是最简单的数据结构
 * 其实栈才是最难的 哭了
 *
 * @author Wenhao Tong
 * @Description
 * @create 2021-07-09 12:50
 */
public class LeetCode316 {
    public static void main(String[] args) {
        LeetCode316 leetCode316 = new LeetCode316();
        String result = leetCode316.removeDuplicateLetters("ccbcbacdcbc");
        System.out.println(result);
    }

    public String removeDuplicateLetters(String s) {

        // 使用一个数组记录当前的字符在记录结果的栈里面是不是已经出现过了
        boolean[] seen = new boolean[26];
        // 记录栈里面的元素是不是可以删除，因为如果只剩下一个的话是不可以删除的
        int[] count = new int[26];
        for (int i = 0;i < s.length();i++) {
            count[s.charAt(i) - 'a']++;
        }
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0;i < s.length();i++) {
            char c = s.charAt(i);
            // 如果当前的元素是stack里面没有的，需要看看他应该排到哪里
            // 原则就是在维护相对次序不变的情况下（stack里面），如果他前面的元素比他大并且是可以删除的，那么立刻删除
            if (!seen[c - 'a']) {
                // 如果后面出现的元素字典序比前面的元素字典序要小，并且前面的元素都是可以删除的，那么当然是全部删除掉啊
                while (stack.size() > 0 && c < stack.peek() && count[stack.peek() - 'a'] >= 1) {
                    // 被删掉之后seen要置为false，意思是这个字符没有出现在结果里面，后面出现的时候要确定他合适的位置
                    seen[stack.pop() - 'a'] = false;
                }
                seen[c - 'a'] = true;
                // 当前的字符找到了合适的位置
                stack.push(c);
            }
            // 如果已经有了，那么说明这个字符已经在合适的位置，排下一个字符吧
            count[c - 'a']--;
        }
        StringBuilder result = new StringBuilder();
        while (stack.size() > 0) {
            result.append(stack.pollLast());
        }
        return result.toString();
    }
}
